//判断一棵二叉树是否堆成
//需要遍历以轴为准的外侧和内侧，则相当于按后序遍历但左右中和右左中的顺序遍历两次
//但不可以直接使用右左中的顺序来比较，使用两种遍历顺序得到的数组即使相同也不一定能构造成同一棵二叉树，不能保证对称
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
};

//递归法
//比较左右两棵树，就相当于比较两颗不同的树
//比较结点数值是否相同，先确定结点是否为空
//两个都空，相同
//一个空，不同
//两个都不空，比较数值
//最后分内外两侧分别比较，内外都相同就说明是一棵对称的二叉树
bool compare(TreeNode* left,TreeNode* right)
{
    if(!left&&!right) return true;  //这句要放前面，因为下一句也包括了两结点都空的情况，而若全空，应该是相同
    else if(!left||!right) return false;
    else if(left->val!=right->val) return false;//用else if 因为如果数值正确，就进行下面的比较

    bool outside=compare(left->left,right->right);
    bool inside=compare(left->right,right->left);

    return inside&&outside;
}

bool isSymmetric_recursion(TreeNode* root)
{
    if(!root) return true;
    return compare(root->right,root->right);    //实际上是用左右两棵子树在比较
}


//迭代法（使用队列）
//使用队列将要进行判断的结点放到队列中，每次出队两个（分别是内侧或外侧的一对），然后将出队结点的左右结点按照顺序入队，确保每次比较都是对称位置比较
#include <queue>
using std::queue;
bool isSymmetric_queue(TreeNode* root)
{
    if(!root) return true;
    queue<TreeNode*> que;
    que.push(root->left);       //1
    que.push(root->right);
    while(!que.empty())
    {
        TreeNode* leftnode=que.front(); que.pop();
        TreeNode* rightnode=que.front(); que.pop();
        if(!leftnode&&!rightnode)  continue; //这句很重要，如果是空结点就不需要进行下面的比较操作
        if(!leftnode||!rightnode||(rightnode->val!=leftnode->val))//一个不存在或者值不等
        return false;

        //相同，进行入队.要按照内侧或者外侧两个结点一起入队，那一侧先入没关系，但一定要对称
        //内侧
        que.push(leftnode->right);      //2
        que.push(rightnode->left);
        //外侧
        que.push(leftnode->left);       //3
        que.push(rightnode->right);
    }
    return true;
    //如果比较完都没有出现不同，就是对称
}
//在将1、2、3组合的两式两两胡乱交换后会发现，其实都是可以检查是否对称的
//其实只要入队是左右内外侧都同时一起进行，无论顺序怎么样，都是可以的（关键就是对称）
//由这个现象看来，使用栈其实也是可以的，因为无论栈还是队列，只要保证两个是对称的就可以了

//栈实现
#include <stack>
using std::stack;
bool isSymmetric_stack(TreeNode* root)
{
    if(!root) return true;
    stack<TreeNode*> st;
    st.push(root->left);
    st.push(root->right);
    while(!st.empty())
    {
        TreeNode* leftnode=st.top(); st.pop();
        TreeNode* rightnode=st.top(); st.pop();
        if(!leftnode&&!rightnode) continue;
        if(!leftnode||!rightnode||(leftnode->val!=rightnode->val)) return false;

        //外侧
        st.push(leftnode->left);
        st.push(rightnode->right);
        //外侧
        st.push(leftnode->right);
        st.push(rightnode->left);
    }
    return true;
}

//你会发现，除了que变成st，front变成top，没有其他区别了